// https://leetcode.cn/problems/rotate-list/
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
	int getLength(ListNode* head){
		int i = 0;
		while(head){
			i++;
			head = head->next;
		}
		return i;
	}
	
    ListNode* rotateRight(ListNode* head, int k) {
		int len = getLength(head);
		if(len == 0){
			return head;
		}
		k %= len;
		if(k == 0){
			return head;
		}
		k = len - k;
		
		ListNode * first = head;

		while(k-- && head){
			head = head->next;
		}
		ListNode * tmpK = head;
		
		while(head->next){
			head = head->next;
		}
		
		while(first != tmpK){
			head->next = first;
			head = first;
			first = first->next;
		}
		head->next = nullptr;
		return tmpK;
    }
	
	
	
	ListNode * init(int n){
		ListNode * head = new ListNode(1);
		ListNode * head1 = new ListNode(4);
		ListNode * head2 = new ListNode(3);
		ListNode * head3 = new ListNode(2);
		ListNode * head4 = new ListNode(5);
		ListNode * head5 = new ListNode(2);
		head->next = head1;
		head->next1 = head2;
		head->next2 = head3;
		head->next3 = head4;
		head->next4 = head5;
		return head;
	}
	
	void show(ListNode * head){
		while(head){
			cout << head->val << ",";
			head = head->next;
		}
		cout << endl;
	}
};


int main(){
	Solution so;
	ListNode * head = so.init(2);
	so.show(head);
	ListNode * newHead = so.rotateRight(head, 2);
	so.show(newHead);
	return 0;
}